import java.util.*;
/**
 * 合法括号序列判断:
 * https://www.nowcoder.com/questionTerminal/d8acfa0619814b2d98f12c071aef20d4
 * User: 86187
 * Date: 2022-10-17
 * Time: 7:56
 */
public class Test {
        public static boolean chkParenthesis(String str, int n) {
            // write code here
            if(str == null || n == 0 || str.charAt(0) !='(')
                return false;
            if(n % 2 != 0)
                return false;

            char[] array = str.toCharArray();
            Stack<Character> stack = new Stack<>();
            int i = 0;
            while(i < n) {
                if(array[i] == '(')
                    stack.push(array[i]);
                else if(!stack.empty() && array[i] == ')')
                    stack.pop();
                else
                    break;
                ++i;
            }
            return stack.empty() && i >= n;
        }

        public static void main(String[] args) {
            System.out.println(chkParenthesis("()(),", 4));
            System.out.println(chkParenthesis("()))))()(d",10));
        }
}
